Сгенерируйте n-ую строку Фибоначчи, которая определяется следующей рекуррентной
формулой:
·
f(0)
= “a”;
·
f(1)
= “b”;
·
f(n) = f(n – 1) + f(n – 2), где
операция “+” означает конкатенацию
Например, f(3) = f(2) + f(1) = (f(1)
+ f(0)) + f(1) = “b” + “a” + “b” = “bab”.
Вход. Одно
целое число n (0 ≤ n ≤ 20).
Выход. Выведите n-ую строку Фибоначчи.
|
Пример входа 1 |
Пример выхода 1 |
|
3 |
bab |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
5 |
babbabab |
рекурсия
Реализуем
рекурсивную функцию, генерирующую n-ую
строку Фибоначчи.
Реализация алгоритма
Функция f
возвращает n-ую строку Фибоначчи.
string f(int n)
{
if (n == 0) return "a";
if (n == 1) return "b";
return f(n-1) + f(n-2);
}
Читаем значение n
и выводим n-ую строку Фибоначчи.
cin >> n;
cout << f(n) << endl;
Реализация алгоритма – без STL
#include <stdio.h>
int n;
void f(int
n)
{
if (n == 0)
{
printf("a"); return;
}
if (n == 1)
{
printf("b"); return;
}
f(n-1);
f(n-2);
}
int main(void)
{
scanf("%d",&n);
f(n); printf("\n");
return 0;
}
Java реализация
import java.util.*;
public class Main
{
static String f(int n)
{
if (n == 0) return "a";
if (n == 1) return "b";
return f(n - 1) + f(n - 2);
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
System.out.println(f(n));
con.close();
}
}
Python реализация
def f(n):
if n == 0:
return "a"
elif n == 1:
return "b"
else:
return f(n-1) + f(n-2)
n = int(input())
print(f(n))